/*
Morris遍历: cur表示当前节点， mostRight表示cur.left(左子树)中的最右节点
1. 如果mostRight为null， cur = cur.right
2. 如果mostRight不为null:
      -- mostRight.right为null, 则mostRight.right = cur(为了能回到cur)， cur = cur.left
      -- mostRight.right为cur, 则mostRight.right = null, cur=cur.right

Morris遍历特点：
   有左子树的节点会访问两次
 */

/**
 * @param {Node} root
 */
function morrisTraversal (root) {
  let cur = root
  while (cur) {
    let mostRight = cur.left
    if (mostRight) {
      while (mostRight.right && mostRight.right !== cur) {
        mostRight = mostRight.right
      }
      if (!mostRight.right) {
        mostRight.right = cur
        cur = cur.left
        continue
      } else {
        mostRight.right = null
      }
    }
    cur = cur.right
  }
}

/**
 * Morris前序遍历
 * @param {Node} root
 */
function morrisPreOrder (root) {
  let cur = root
  while (cur) {
    let mostRight = cur.left
    if (mostRight) {
      while (mostRight.right && mostRight.right !== cur) {
        mostRight = mostRight.right
      }
      if (!mostRight.right) {
        mostRight.right = cur
        console.log(cur.value) // cur有左子树，第一次来到该节点
        cur = cur.left
        continue
      } else {
        mostRight.right = null
      }
    } else {
      console.log(cur.value)// cur没有左子树，第一次来到该节点
    }
    cur = cur.right
  }
}

/**
 * Morris中序遍历
 * @param {Node} root
 */
function morrisInOrder (root) {
  let cur = root
  while (cur) {
    let mostRight = cur.left
    if (mostRight) {
      while (mostRight.right && mostRight.right !== cur) {
        mostRight = mostRight.right
      }
      if (!mostRight.right) {
        mostRight.right = cur
        cur = cur.left
        continue
      } else {
        mostRight.right = null
      }
    }
    // Morris遍历对于没有左子树的节点只访问一次，可以理解成"左中"访问就是一次，那么只要在它向右跑之前打印就行
    console.log(cur.value)
    cur = cur.right
  }
}

/**
 * Morris后序遍历: 对于只能到达1次的节点，直接跳过
 * 如果第二次到达X时，逆序打印x.left的右边界
 * @param root
 */
function morrisPostOrder (root) {
  let cur = root
  while (cur) {
    let mostRight = cur.left
    if (mostRight) {
      while (mostRight.right && mostRight.right !== cur) {
        mostRight = mostRight.right
      }
      if (!mostRight.right) {
        mostRight.right = cur
        cur = cur.left
        continue
      } else {
        mostRight.right = null
        reverseTraversalRightEdge(cur.left) // 第二次到达该节点
      }
    }
    cur = cur.right
  }
  reverseTraversalRightEdge(root)
}

/**
 * @param {Node} node
 */
function reverseTraversalRightEdge (node) {
  const reversedNode = reverseRightEdge(node)
  for (let cur = reversedNode; cur !== null; cur = cur.right) {
    console.log(cur.value)
  }
  reverseRightEdge(reversedNode)
}

/**
 * @param {Node} node
 */
function reverseRightEdge (node) {
  let prev = null
  let cur = node
  while (cur) {
    const next = cur.right
    cur.right = prev
    prev = cur
    cur = next
  }
  return prev
}
